//
// Created by ASUS on 2025/10/14.
//
#include <iostream>
#include <cstdint>
#include <string>
#include <cmath>
#include <bitset>
#ifndef DBLEARN_CMU15445_HYPERLOGLOG_H
#define DBLEARN_CMU15445_HYPERLOGLOG_H

#endif //DBLEARN_CMU15445_HYPERLOGLOG_H

/*
 * 总结
 * 1.HLL算法的正确性源于概率上的推理，通过前导0的数量来估算集合的基数是多少。
 * 比如一个字符串得到哈希值之后，有k位前导0,即0000......00001的概率是(1/2)^(k+1)，
 * 前k个是0，第k+1个是1，这意味着大约有2^(k+1)个单独的字符串出现，才会产生这样一个有k位前导0的哈希值，
 * 从而估计出此时的基数大约是2^(k+1)，再考虑一些如方差等统计学上的细节，加入分桶平均等方法，最终形成了HLL算法。
 * 2.还有一种presto实现方式，桶里的内容存储的是最右边的连续为0位的数量
 */

// 简单的 MurmurHash3 启发式实现
uint64_t murmurhash3_64(const void* key, int len, uint32_t seed = 0) {
    const uint64_t m = 0xc6a4a7935bd1e995ULL;
    const int r = 47;

    const uint8_t* data = (const uint8_t*)key;
    const uint8_t* end = data + len;

    uint64_t h = seed ^ (len * m);

    while (data + 8 <= end) {
        uint64_t k = *(uint64_t*)data;

        k *= m;
        k ^= k >> r;
        k *= m;

        h ^= k;
        h *= m;

        data += 8;
    }

    // 处理剩余字节
    uint64_t k = 0;
    switch (end - data) {
        case 7: k ^= uint64_t(data[6]) << 48;
        case 6: k ^= uint64_t(data[5]) << 40;
        case 5: k ^= uint64_t(data[4]) << 32;
        case 4: k ^= uint64_t(data[3]) << 24;
        case 3: k ^= uint64_t(data[2]) << 16;
        case 2: k ^= uint64_t(data[1]) << 8;
        case 1: k ^= uint64_t(data[0]);
            k *= m;
            k ^= k >> r;
            k *= m;
            h ^= k;
    }

    h ^= h >> r;
    h *= m;
    h ^= h >> r;

    return h;
}


template <typename T>
class HyperLogLog{
private:
    int initial_bits;
    double cardinality;
    int* registers;
    int register_cnt;
    double alpha_m;

public:
    HyperLogLog(int initial_bits){
        this->initial_bits = initial_bits;
        cardinality = 0;
        register_cnt = (int)pow(2, this->initial_bits);
        this->registers = new int [register_cnt];
        for (int i = 0; i < this->register_cnt; i++) {
            this->registers[i] = 0;
        }
        switch (register_cnt) {
            case 16:
                alpha_m = 0.673;
                break;
            case 32:
                alpha_m = 0.697;
                break;
            case 64:
                alpha_m = 0.709;
                break;
            default:
                if (register_cnt >= 128) {
                    alpha_m = 0.7213 / (1.0 + 1.079 / register_cnt);
                }
        }
    }

    ~HyperLogLog(){
        delete[] registers;
    }

    double GetCardinality(){
        return cardinality;
    }

    void AddElem(T& val){
        uint64_t hashcode = murmurhash3_64(val.data(), val.length());
        int register_index = hashcode >> (64 - initial_bits);

//        std::bitset<64> bits(hashcode);
//        std::cout << "binary:" << bits << std::endl;

        hashcode = hashcode << initial_bits;
        int zero_count = 0;
        while (((hashcode & (1ULL << 63)) == 0) && (zero_count < 64 - initial_bits)) {
            hashcode = hashcode << 1;
            zero_count++;
        }

        registers[register_index] = std::max(registers[register_index], zero_count + 1);
        ComputeCardinality();
    }
private:
    void ComputeCardinality(){
        double sum = 0;
        for (int i = 0; i < this->register_cnt; i++) {
            sum += pow(2, -registers[i]);
        }
        double z = register_cnt / sum;
        cardinality = alpha_m * register_cnt * z;
    }
};